package algorithm.binaryTreeAlgorithm;

import data.Node;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName: LevelOrder
 * @Description 429. N 叉树的层序遍历
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 *
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * @Author skywingking
 * @Date 2022/4/8 10:53 下午
 **/
public class LevelOrder {
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int cnt = queue.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < cnt;i++){
                Node cur = queue.poll();
                level.add(cur.val);
                for (Node child : cur.children) {
                    queue.offer(child);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}